//
//  Problem16.swift
//  LeetCode - 16 - 最接近的三数之和
//
//  Created by 武侠 on 2020/7/6.
//  Copyright © 2020 zhulongiMac02. All rights reserved.
//

import UIKit

/*
 [16 最接近的三数之和]
 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

 示例：
 输入：nums = [-1,2,1,-4], target = 1
 输出：2
 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
  

 提示：
 3 <= nums.length <= 10^3
 -10^3 <= nums[i] <= 10^3
 -10^4 <= target <= 10^4
 
   -1 -1 0 1 2 3  100
   90:
   98  -1 -1 100
   1   -1 -1 3
   2   -1 0 3
   3   -1 1 3
   4   -1 2 3

   99  -1 0 100
   2   -1 0 3
   3   -1 1 3
   4   -1 2 3

  101  0 1 100
 */
class Problem16: NSObject {
    func solution() {

//        print("n = 4", generateParenthesis(4))
//            print(threeSumClosest([-1,2,1,-4], 1))
//        print(threeSumClosest([-1, -1, 0, 1, 2, 3,  100], 90))
//        print(threeSumClosest([1,1,1,1], -100))
        print("result =", threeSumClosest([0,2,1,-3], 1))
    }
    // 思路:
    // 1: 先排序
    // 2: 2层循环, 第一层定位i, 第二层 双指针, j + l  >时, j++; <时, l--
    func threeSumClosest(_ nums: [Int], _ target: Int) -> Int {
        
        
        // 1: 先排序
        var lists = nums
        lists.sort()
        print(lists)
        
        var vesc = lists[0] + lists[1] + lists[2]
        // 2:
        for i in 0..<lists.count - 2 {
            print("i = ", lists[i])
            if i > 0, lists[i] == lists[i - 1] {
                continue
            }
            var j = i + 1
            var l = lists.count - 1
            
            while j < l {
                
                let tempVesc = lists[i] + lists[j] + lists[l]
                print(vesc, tempVesc, lists[i], lists[j], lists[l])
                print("abs = ", tempVesc - target, vesc - target, abs(tempVesc - target), abs(vesc - target))
                if abs(tempVesc - target) < abs(vesc - target) {
                    vesc = tempVesc
                    print("vesc = ", vesc)
                }
                
                if tempVesc < target {
                    j += 1
                    while j < l, lists[j] == lists[j-1] {
                        j += 1
                    }
                } else if tempVesc > target {
                    l -= 1
                    while l > j, lists[l] == lists[l+1] {
                        l -= 1
                    }
                } else {
                    return target
                }
                
            }
        }
        
        return vesc
    }
}
